#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


//
//void existDfs(vector<vector<char>> &board, string word, int nrow, int ncol, int k,string s, vector<vector<int>>& dp) {
//    int row = board.size() - 1;
//    int col = (board[0].size() - 1);
//    if (nrow < 0 || nrow > row)
//        return;
//    if (ncol < 0 || ncol > col)
//        return;
//
//    if (k >= word.size())
//        return;
//
//    if (dp[nrow][ncol]==1)
//        return;
//
//    char a=board[nrow][ncol];
//    char wk=word[k];
//    if (wk == a) {
//        dp[nrow][ncol]=1;
//        if ((s+a).compare(word) == 0)
//        {
//            isPass = true;
//            return;
//        }
//
//    }
//
//
//   // s += board[nrow][ncol];
//
//    existDfs(board, word, nrow + 1, ncol, k+1,s+ board[nrow][ncol],dp);
//    existDfs(board, word, nrow - 1, ncol, k+1,s+ board[nrow][ncol],dp);
//    existDfs(board, word, nrow, ncol + 1, k+1,s+ board[nrow][ncol],dp);
//    existDfs(board, word, nrow, ncol - 1, k+1,s+ board[nrow][ncol],dp);
//
//}
//
////对开始进行一次dfs
//void dfs(vector<vector<char>> &board, string word, int nrow, int ncol, int k,string s, vector<vector<int>>& dp) {
//    if (isPass)
//        return;
//
//    int row = board.size() - 1;
//    int col = (board[0].size() - 1);
//    if (nrow < 0 || nrow > row)
//        return;
//    if (ncol < 0 || ncol > col)
//        return;
//
//    if (k >= word.size())
//        return;
//
//    if (dp[nrow][ncol]==1)
//        return;
//
//    char a=board[nrow][ncol];
//    char wk=word[k];
//    if (wk == a) {
//        dp[nrow][ncol]=1;
//        if ((s+a).compare(word) == 0)
//        {
//            isPass = true;
//            return;
//        }
//
//    }
//
//
//    dfs(board, word, nrow + 1, ncol, k+1,s+ board[nrow][ncol],dp);
//    dfs(board, word, nrow - 1, ncol, k+1,s+ board[nrow][ncol],dp);
//    dfs(board, word, nrow, ncol + 1, k+1,s+ board[nrow][ncol],dp);
//    dfs(board, word, nrow, ncol - 1, k+1,s+ board[nrow][ncol],dp);
//
//
//}
//
//
//
//bool exist(vector<vector<char>> &board, string word) {
//    int row = board.size() - 1;
//    int col = (board[0].size() - 1);
//    vector<vector<int>> dp(100, vector<int>(100, 0));
//
//    string s="";
//   // existDfs(board, word, 0, 0, 0,s,dp);
//
//    for (int i = 0; i <=row ; ++i) {
//        for (int j = 0; j <=col ; ++j) {
//            dfs(board, word, i, j, 0,s,dp);
//        }
//    }
//
//    return isPass;
//
//}


//bool exist(vector<vector<char>>& board, string word) {
//
//
//    int row = board.size() - 1;
//    int col = (board[0].size() - 1);
//    vector<vector<int>> visited(row+1, vector<int>(col+1, 0));
//    for (int i = 0; i <=row ; ++i) {
//
//        for (int j = 0; j <=col ; ++j) {
//            if(isPass)
//                return true;
//
//            back(board,  word, i,j,0,visited);
//
//
//        }
//
//    }
//
//    return isPass;
//}




//todo
bool isPass = false;

//void back(vector<vector<char>>& board, string word,int nowRow,int nowCol,int k,vector<vector<int>> visited)
//{
//    if (isPass)
//        return;
//    int row = board.size() - 1;
//    int col = (board[0].size() - 1);
//    if (nowRow < 0 || nowRow > row)
//        return;
//    if (nowCol < 0 || nowCol > col)
//        return;
//    //如果已经访问就ret
//    if (visited[nowRow][nowCol]==1)
//        return;
//    if (k >= word.size())
//        return;
//
//    if (word[k]!=board[nowRow][nowCol])
//    {
//        return;
//    }
//
//    if (word[k]==board[nowRow][nowCol]&&k==word.size()-1)
//    {
//        isPass= true;
//    }
//
//
//    visited[nowRow][nowCol]=1;
//
//    back(board,word,nowRow+1,nowCol,k+1,visited);//注意这里是k+1 不是k++
//    back(board,word,nowRow-1,nowCol,k+1,visited);
//    back(board,word,nowRow,nowCol+1,k+1,visited);
//    back(board,word,nowRow,nowCol-1,k+1,visited);
//
//    visited[nowRow][nowCol]=0;//回退初试环境
//
//
//}


//这道题真的干 他妈的 这个必须是引用 否则 速度很慢的导致挂了
bool back(vector<vector<char>> &board, string word, int nowRow, int nowCol, int k, vector<vector<int>> &visited) {

    int row = board.size() - 1;
    int col = (board[0].size() - 1);
    if (nowRow < 0 || nowRow > row || nowCol < 0 || nowCol > col || visited[nowRow][nowCol] == 1 || k >= word.size() ||
        word[k] != board[nowRow][nowCol])
        return false;

    if (k == word.size() - 1) {
        return true;
    }


    visited[nowRow][nowCol] = 1;

    //注意这里是k+1 不是k++
    bool ret = back(board, word, nowRow + 1, nowCol, k + 1, visited) ||
               back(board, word, nowRow - 1, nowCol, k + 1, visited) ||
               back(board, word, nowRow, nowCol + 1, k + 1, visited) ||
               back(board, word, nowRow, nowCol - 1, k + 1, visited);

    visited[nowRow][nowCol] = 0;// 回退初试环境 他会把赋值为1 的全部归为的

    return ret;

}

bool exist(vector<vector<char>> &board, string word) {


    int row = board.size() - 1;
    int col = (board[0].size() - 1);
    vector<vector<int>> visited(row + 1, vector<int>(col + 1, 0));
    for (int i = 0; i <= row; ++i) {

        for (int j = 0; j <= col; ++j) {


            if (back(board, word, i, j, 0, visited))
                return true;

        }

    }

    return false;
}

//todo 总结 这道题犯了错误
// 1下面k+1 不应该写成 k++
// 2 关于只能找没访问过的 需要在函数前 赋值为 true 之后 赋值为 false  自己看 一下那个函数 原来一直不理解为啥要之后要赋值为false
// 其实整体想就行了 为啥之后要赋值为false 回退初试环境 他会把赋值为1 的全部归0的 其实想着 这个函数执行完赋值为0 不影响下一个for （i，j）就行

//board[row][col] = '*';
//if (backtrack(board, row - 1, col, word, idx + 1) ||
//backtrack(board, row + 1, col, word, idx + 1) ||
//backtrack(board, row, col - 1, word, idx + 1) ||
//backtrack(board, row, col + 1, word, idx + 1))
//return true;
//
//board[row][col] = word[idx]; 网上还有这种写法 这个肯定是数组里面的数了 因为前面不对直接返回了
/*
 *     int rowMax=0;
    int colMax=0;
    vector<vector<bool> >vi;
    int ret=false;
    bool exist_r(vector<vector<char>>& board,const string& word,string temp,int row,int col) {


        if(row>rowMax || col>colMax ||row<0||col<0 ||vi[row][col])
            return false;

        if(temp.size()+1>word.size())
        {
            return false;
        }

        if(temp.size()+1==word.size()&&(temp+board[row][col]).compare(word)==0)
        {
            ret=true;
            return true;
        }

       if(temp.size()+1==word.size()&&(temp+board[row][col]).compare(word)!=0)
          return false;

        if(ret)
        return ret;

        vi[row][col]=true;//妈蛋这个得放在这边

        auto ttt=( exist_r(board,word,temp+board[row][col],row+1,col)||
        exist_r(board,word,temp+board[row][col],row-1,col)||
        exist_r(board,word,temp+board[row][col],row,col+1)||
        exist_r(board,word,temp+board[row][col],row,col-1));

       vi[row][col]=false;
             return ttt;
         }


    bool exist(vector<vector<char>>& board, string word) {
            rowMax=board.size()-1;
            colMax=board[0].size()-1;

            vi.resize(rowMax+1,vector<bool>(colMax+1,false));

            for(int i=0;i<=rowMax;i++)
            {
            for(int j=0;j<=colMax;j++)
            {
                ret=false;
                if(exist_r(board,word,"",i,j))
                 return true;
            }
            }


        return false;

    }
 *
 * 后来重新刷的时候出现另外问题  第一个是没有嵌套那个俩for循环 另外一个是没有设置visit 以及visit的位置设置错了
 * 还有尽量不要设置字符串相加 都会超时的 用下标++
 * */